package _18_剑指OfferII;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class _074_剑指OfferII合并区间 {

    public static void main(String[] args) {

        _074_剑指OfferII合并区间 v = new _074_剑指OfferII合并区间();


        int[][] ins = {{1,3},{2,1},{8,10},{15,18}};
        System.out.println(Arrays.deepToString(v.merge(ins)));

    }

    public int[][] merge(int[][] intervals) {
        // 按照首数字排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> results = new ArrayList<>();
        results.add(intervals[0]);

        int preIndex = 0;
        for (int i = 1; i < intervals.length; ++i) {
            int start = intervals[i][0];
            int last = intervals[i][1];
            int preLast = results.get(preIndex)[1];
            if (preLast < start) {
                preIndex = results.size();
                // 区间不重叠
                results.add(intervals[i]);
            } else if (last > preLast){
                // 区间重叠, 合并区间，并且更换
                results.get(preIndex)[1] = last;
            }
        }
        return results.toArray(new int[0][]);
    }

}
